package dp.test91;

import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/22 13:16
 */
public class Solution1 {

    // map做缓存， 递归
    HashMap<String, Integer> map = new HashMap<>();

    public int numDecodings(String s) {
        if (s == null || s.equals("")) return 1;
        if (s.charAt(0) == '0') return 0;
        if (map.containsKey(s)) return map.get(s);
        if (s.length() == 1) return 1;
        int num = (s.charAt(0) - '0') * 10 + (s.charAt(1) - '0');
        int ans;
        if (num <= 26) {
            ans = numDecodings(s.substring(1)) + numDecodings(s.substring(2));
        } else {
            ans = numDecodings(s.substring(1));
        }
        map.put(s, ans);
        return ans;
    }
}
